class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = {}
        self.flag = -1


class Solution(object):
    def minimumLengthEncoding(self, words):
        tree = Node('#')
        for index, word in enumerate(words):
            word = word[::-1]
            node = tree
            for c in word:
                if c not in node.neighbors:
                    node.flag = -1
                    new_node = Node(c)
                    node.neighbors[c] = new_node
                    node = new_node
                else:
                    node = node.neighbors[c]
            if not node.neighbors:
                node.flag = index
        self.t = 0

        def search(node):
            if not node.neighbors:
                self.t += len(words[node.flag]) + 1
            for key in node.neighbors:
                search(node.neighbors[key])

        search(tree)
        return self.t


data = Solution()
words = ["time", "me", "bell"]
print(data.minimumLengthEncoding(words))
words = ["t"]
print(data.minimumLengthEncoding(words))
words = ["p", "grah", "qwosp"]
print(data.minimumLengthEncoding(words))
